#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <iomanip>
#include <queue>
#include <algorithm>

struct Process {
    std::string name;
    int arrivalTime;
    int serviceTime;
    int startTime;
    int endTime;
    float turnaroundTime;
    float weightedTurnaroundTime;
};

bool compareArrivalTimes(const Process& a, const Process& b) {
    return a.arrivalTime < b.arrivalTime;
}

void calculateTimes(std::vector<Process>& processes) {
    std::sort(processes.begin(), processes.end(), compareArrivalTimes);

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    int currentTime = 0;
    int index = 0;
    int n = processes.size();

    while (index < n || !pq.empty()) {
        if (pq.empty() && currentTime < processes[index].arrivalTime) {
            currentTime = processes[index].arrivalTime;
        }

        while (index < n && currentTime >= processes[index].arrivalTime) {
            pq.push({ processes[index].serviceTime, index });
            index++;
        }

        auto currentProcess = pq.top();
        pq.pop();
        int processIndex = currentProcess.second;

        processes[processIndex].startTime = currentTime;
        processes[processIndex].endTime = currentTime + processes[processIndex].serviceTime;
        processes[processIndex].turnaroundTime = processes[processIndex].endTime - processes[processIndex].arrivalTime;
        processes[processIndex].weightedTurnaroundTime = processes[processIndex].turnaroundTime / processes[processIndex].serviceTime;

        currentTime = processes[processIndex].endTime;
    }
}

int main() {

    std::cout << "<<----------非抢占式短进程优先算法---------->>\n" << std::endl;

    int n;
    std::cout << "请输入进程数目: ";
    std::cin >> n;

    std::vector<Process> processes(n);
    std::cout << "\n请依次输入各个进程的信息（格式：进程名称 到达时间 服务时间）：" << std::endl;
    for (int i = 0; i < n; ++i) {
        std::cout << "请输入进程 " << i + 1 << "的信息: ";
        std::cin >> processes[i].name >> processes[i].arrivalTime >> processes[i].serviceTime;
    }

    calculateTimes(processes);

    std::cout << "\n调用非抢占式短进程优先算法以后进程的运行顺序为：";
    std::vector<Process> sortedProcesses = processes;
    std::sort(sortedProcesses.begin(), sortedProcesses.end(), [](const Process& a, const Process& b) {
        return a.startTime < b.startTime;
        });
    for (const auto& process : sortedProcesses) {
        std::cout << process.name;
        if (&process != &sortedProcesses.back()) {
            std::cout << " --> ";
        }
    }

    std::cout << "\n具体进程调度信息：\n" << std::endl;

    std::cout << "进程名\t到达时间\t服务时间\t开始时间\t结束时间\t周转时间\t带权周转时间" << std::endl;
    float totalTurnaroundTime = 0, totalWeightedTurnaroundTime = 0;
    for (const auto& process : processes) {
        std::cout << process.name << "\t"
            << std::fixed << std::setprecision(3) << process.arrivalTime << "\t\t"
            << std::fixed << std::setprecision(3) << process.serviceTime << "\t\t"
            << std::fixed << std::setprecision(3) << process.startTime << "\t\t"
            << std::fixed << std::setprecision(3) << process.endTime << "\t\t"
            << std::fixed << std::setprecision(3) << process.turnaroundTime << "\t\t"
            << std::fixed << std::setprecision(3) << process.weightedTurnaroundTime << std::endl;
        totalTurnaroundTime += process.turnaroundTime;
        totalWeightedTurnaroundTime += process.weightedTurnaroundTime;
    }

    std::cout << "\n平均周转时间为: " << std::fixed << std::setprecision(3) << (totalTurnaroundTime / n) << std::endl;
    std::cout << "平均带权周转时间为: " << std::fixed << std::setprecision(3) << (totalWeightedTurnaroundTime / n) << std::endl;

    return 0;
}



